//
// Description: 63. 不同路径 II
// Created by Loading on 2022/6/11.
//

#include <bits/stdc++.h>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
    int n = obstacleGrid.size();
    int m = obstacleGrid[0].size();
    // 起点或终点有障碍，直接返回 0
    if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) {
        return 0;
    }

    // dp[i][j] 表示从起点到 (i,j) 位置，不同的路径数
    int dp[n][m];
    memset(dp, 0, sizeof dp);

    // 初始化
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        if (obstacleGrid[i][0] == 0) {
            dp[i][0] = dp[i - 1][0];
        }
    }
    for (int i = 1; i < m; ++i) {
        if (obstacleGrid[0][i] == 0) {
            dp[0][i] = dp[0][i - 1];
        }
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (obstacleGrid[i][j] == 0) {
                // 没有障碍时，可通过上方和左方的路径数转移而来
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    return dp[n - 1][m - 1];
}

int main() {
    vector<vector<int>> obstacleGrid = {{0, 0, 0},
                                        {0, 1, 0},
                                        {0, 0, 0}};

    auto res = uniquePathsWithObstacles(obstacleGrid);

    cout << res << endl;

    return 0;
}